`:top

In `F33f`_`[decision tree learning`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Decision_tree_learning]`_`f, `!ID3`! (`!Iterative Dichotomiser 3`!) is an `F33f`_`[algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Algorithm]`_`f invented by `F33f`_`[Ross Quinlan`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Ross_Quinlan]`_`f`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] used to generate a `F33f`_`[decision tree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Decision_tree_learning]`_`f from a dataset. ID3 is the precursor to the `F33f`_`[C4.5 algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=C4.5_algorithm]`_`f, and is typically used in the `F33f`_`[machine learning`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Machine_learning]`_`f and `F33f`_`[natural language processing`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Natural_language_processing]`_`f domains.

>>Contents

• `F0af`_`[Algorithm`#algorithm]`_`f

• `F0af`_`[Summary`#summary]`_`f

• `F0af`_`[Properties`#properties]`_`f

• `F0af`_`[Usage`#usage]`_`f

• `F0af`_`[The ID3 metrics`#the-id3-metrics]`_`f

• `F0af`_`[Entropy`#entropy]`_`f

• `F0af`_`[Information gain`#information-gain]`_`f

• `F0af`_`[See also`#see-also]`_`f

• `F0af`_`[References`#references]`_`f

• `F0af`_`[Further reading`#further-reading]`_`f

• `F0af`_`[External links`#external-links]`_`f

-─

>>Algorithm

The ID3 algorithm begins with the original set S {\\displaystyle S} as the `F33f`_`[root node`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Root_node]`_`f. On each `F33f`_`[iteration`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Iteration]`_`f of the algorithm, it iterates through every unused `F33f`_`[attribute`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Feature_(machine_learning)]`_`f of the set S {\\displaystyle S} and calculates the `F33f`_`[entropy`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Entropy_(information_theory)]`_`f H ( S ) {\\displaystyle \\mathrm {H} {(S)}} or the `F33f`_`[information gain`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Information_gain_in_decision_trees]`_`f I G ( S ) {\\displaystyle IG(S)} of that attribute. It then selects the attribute which has the smallest entropy (or largest information gain) value. The set S {\\displaystyle S} is then split or `F33f`_`[partitioned`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Partition_of_a_set]`_`f by the selected attribute to produce subsets of the data. (For example, a node can be split into `F33f`_`[child nodes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Child_node]`_`f based upon the subsets of the population whose ages are less than 50, between 50 and 100, and greater than 100.) The algorithm continues to `F33f`_`[recurse`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Recursion_(computer_science)]`_`f on each subset, considering only attributes never selected before.

Recursion on a subset may `F33f`_`[stop`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Base_case_(recursion)]`_`f in one of these cases:

• every element in the subset belongs to the same class; in which case the node is turned into a `F33f`_`[leaf node`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Leaf_node]`_`f and labelled with the class of the examples.

• there are no more attributes to be selected, but the examples still do not belong to the same class. In this case, the node is made a leaf node and labelled with the `F33f`_`[most common class`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Mode_(statistics)]`_`f of the examples in the subset.

• there are `F33f`_`[no examples in the subset`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Empty_set]`_`f, which happens when no example in the parent set was found to match a specific value of the selected attribute. An example could be the absence of a person among the `F33f`_`[population`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Population_(statistics)]`_`f with age over 100 years. Then a leaf node is created and labelled with the most common class of the examples in the parent node's set.

Throughout the algorithm, the decision tree is constructed with each non-terminal node (`F33f`_`[internal node`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Internal_node]`_`f) representing the selected `F33f`_`[attribute`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Feature_(machine_learning)]`_`f on which the data was split, and terminal nodes (leaf nodes) representing the class label of the final subset of this branch.

>>>Summary

1. Calculate the `F33f`_`[entropy`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Entropy_(information_theory)]`_`f of every `F33f`_`[attribute`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Feature_(machine_learning)]`_`f a {\\displaystyle a} of the data set S {\\displaystyle S} .

2. Partition ("split") the set S {\\displaystyle S} into `F33f`_`[subsets`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Subset]`_`f using the attribute for which the `F33f`_`[resulting`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Posterior_distribution]`_`f entropy after splitting is `F33f`_`[minimized`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Minimum]`_`f; or, equivalently, information gain is `F33f`_`[maximum`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Maximum]`_`f.

3. Make a decision tree `F33f`_`[node`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Node_(computer_science)]`_`f containing that attribute.

4. Recurse on subsets using the remaining attributes.

>>>Properties

ID3 does not guarantee an optimal solution. It can converge upon `F33f`_`[local optima`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Local_optimum]`_`f. It uses a `F33f`_`[greedy strategy`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Greedy_algorithm]`_`f by selecting the locally best attribute to split the dataset on each iteration. The `F33f`_`[algorithm's optimality`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Algorithm's_optimality]`_`f can be improved by using `F33f`_`[backtracking`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Backtracking]`_`f during the search for the optimal decision tree at the cost of possibly taking longer.

ID3 can `F33f`_`[overfit`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Overfitting]`_`f the training data. To avoid overfitting, smaller decision trees should be preferred over larger ones. This algorithm usually produces small trees, but it does not always produce the smallest possible decision tree.

ID3 is harder to use on continuous data than on factored data (factored data has a discrete number of possible values, thus reducing the possible branch points). If the values of any given attribute are `F33f`_`[continuous`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Continuous_variable]`_`f, then there are many more places to split the data on this attribute, and searching for the best value to split by can be time-consuming.

>>>Usage

The ID3 algorithm is used by training on a `F33f`_`[data set`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Data_set]`_`f S {\\displaystyle S} to produce a `F33f`_`[decision tree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Decision_tree]`_`f which is stored in `F33f`_`[memory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_memory]`_`f. At `F33f`_`[runtime`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Run_time_(program_lifecycle_phase)]`_`f, this decision tree is used to `F33f`_`[classify`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Statistical_classification]`_`f new test cases (`F33f`_`[feature vectors`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Feature_vector]`_`f) by `F33f`_`[traversing`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Tree_traversal]`_`f the decision tree using the features of the datum to arrive at a leaf node.

>>The ID3 metrics

>>>Entropy

`F33f`_`[Entropy`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Entropy_(information_theory)]`_`f H ( S ) {\\displaystyle \\mathrm {H} {(S)}} is a measure of the amount of uncertainty in the (data) set S {\\displaystyle S} (i.e. entropy characterizes the (data) set S {\\displaystyle S} ).

H ( S ) = ∑ ∑ x ∈ ∈ X − − p ( x ) log 2 ⁡ ⁡ p ( x ) {\\displaystyle \\mathrm {H} {(S)}=\\sum _{x\\in X}{-p(x)\\log _{2}p(x)}}

Where,

• S {\\displaystyle S} – The `F33f`_`[current dataset`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Local_variable]`_`f for which entropy is being calculated

• This changes at each step of the ID3 algorithm, either to a subset of the previous set in the case of splitting on an attribute or to a "sibling" partition of the parent in case the recursion terminated previously.

• X {\\displaystyle X} – The set of classes in S {\\displaystyle S}

• p ( x ) {\\displaystyle p(x)} – The `F33f`_`[proportion`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Proportion_(mathematics)]`_`f of the `F33f`_`[number of elements`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cardinality]`_`f in class x {\\displaystyle x} to the number of elements in set S {\\displaystyle S}

When H ( S ) = 0 {\\displaystyle \\mathrm {H} {(S)}=0} , the set S {\\displaystyle S} is perfectly classified (i.e. all elements in S {\\displaystyle S} are of the same class).

In ID3, entropy is calculated for each remaining attribute. The attribute with the `!smallest`! entropy is used to split the set S {\\displaystyle S} on this iteration. Entropy in `F33f`_`[information theory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Information_theory]`_`f measures how much information is `F33f`_`[expected`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Expected_value]`_`f to be gained upon `F33f`_`[measuring`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Sampling_(signal_processing)]`_`f a `F33f`_`[random variable`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Random_variable]`_`f; as such, it can also be used to quantify the amount to which the `F33f`_`[distribution`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Probability_distribution]`_`f of the quantity's values is unknown. A `F33f`_`[constant`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Constant_(mathematics)]`_`f quantity has zero entropy, as its distribution is `F33f`_`[perfectly known`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Complete_information]`_`f. In contrast, a uniformly distributed random variable (`F33f`_`[discretely`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Discrete_uniform_distribution]`_`f or `F33f`_`[continuously`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Continuous_uniform_distribution]`_`f uniform) maximizes entropy. Therefore, the greater the entropy at a node, the less information is known about the classification of data at this stage of the tree; and therefore, the greater the potential to improve the classification here.

As such, ID3 is a `F33f`_`[greedy`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Greedy_algorithm]`_`f `F33f`_`[heuristic`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Heuristic_(computer_science)]`_`f performing a `F33f`_`[best-first search`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Best-first_search]`_`f for `F33f`_`[locally optimal`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Locally_optimal]`_`f entropy values. Its accuracy can be improved by preprocessing the data.

>>>Information gain

`F33f`_`[Information gain`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Information_gain_in_decision_trees]`_`f I G ( A ) {\\displaystyle IG(A)} is the measure of the difference in entropy from before to after the set S {\\displaystyle S} is split on an attribute A {\\displaystyle A} . In other words, how much uncertainty in S {\\displaystyle S} was reduced after splitting set S {\\displaystyle S} on attribute A {\\displaystyle A} .

I G ( S , A ) = H ( S ) − − ∑ ∑ t ∈ ∈ T p ( t ) H ( t ) = H ( S ) − − H ( S | A ) . {\\displaystyle IG(S,A)=\\mathrm {H} {(S)}-\\sum _{t\\in T}p(t)\\mathrm {H} {(t)}=\\mathrm {H} {(S)}-\\mathrm {H} {(S|A)}.}

Where,

• H ( S ) {\\displaystyle \\mathrm {H} (S)} – Entropy of set S {\\displaystyle S}

• T {\\displaystyle T} – The subsets created from splitting set S {\\displaystyle S} by attribute A {\\displaystyle A} such that S = ⋃ ⋃ t ∈ ∈ T t {\\displaystyle S=\\bigcup _{t\\in T}t}

• p ( t ) {\\displaystyle p(t)} – The proportion of the number of elements in t {\\displaystyle t} to the number of elements in set S {\\displaystyle S}

• H ( t ) {\\displaystyle \\mathrm {H} (t)} – Entropy of subset t {\\displaystyle t}

In ID3, information gain can be calculated (instead of entropy) for each remaining attribute. The attribute with the `!largest`! information gain is used to split the set S {\\displaystyle S} on this iteration.

>>See also

• `F33f`_`[Classification and regression tree`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Classification_and_regression_tree]`_`f (CART)

• `F33f`_`[C4.5 algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=C4.5_algorithm]`_`f

• `F33f`_`[Decision tree learning`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Decision_tree_learning]`_`f

• `F33f`_`[Decision tree model`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Decision_tree_model]`_`f

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81–106

`:cite-note-2`!1.`! `:citereftaggartdesimoneshihfilloux2012`aTaggart, Allison J; DeSimone, Alec M; Shih, Janice S; Filloux, Madeleine E; Fairbrother, William G (2012-06-17). "Large-scale mapping of branchpoints in human pre-mRNA transcripts in vivo". `*Nature Structural & Molecular Biology`*. `!19`! (7): 719–721. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1038/nsmb.2327. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 1545-9993. `F33f`_`[PMC`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=PMC_(identifier)]`_`f 3465671. `F33f`_`[PMID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=PMID_(identifier)]`_`f 22705790.

>>Further reading

• `:citerefmitchell1997`aMitchell, Tom Michael (1997). `*Machine Learning`*. New York, NY: McGraw-Hill. pp. 55–58. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 0070428077. `F33f`_`[OCLC`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=OCLC_(identifier)]`_`f 36417892.

• `:citerefgrzymala-busse1993`aGrzymala-Busse, Jerzy W. (February 1993). "Selected Algorithms of Machine Learning from Examples" (PDF). `*Fundamenta Informaticae`*. `!18`! (2): 193–207 – via ResearchGate.

>>External links

• Seminars – http://www2.cs.uregina.ca/

• Description and examples – http://www.cise.ufl.edu/

• Description and examples – http://www.cis.temple.edu/

• Decision Trees and Political Party Classification

`c`F0af`_`[↑ Back to top`#top]`_`f`a